package Map;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

public class MapProblem {
    static class Node {
        int val;
        Node next;
        Node random;

        public Node(int val) {
            this.val = val;
            this.next = null;
            this.random = null;
        }
    }
    //给你一个 非空 整数数组 nums ，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
    //你必须设计并实现线性时间复杂度的算法来解决此问题，且该算法只使用常量额外空间。
    //输入：nums = [2,2,1] 输入：nums = [4,1,2,1,2]
    //输出：1              输出：4
//    public int singleNumber(int[] nums) {
//        // 使用 HashMap 统计每个数字出现的次数
//       // 再遍历 HashMap, 找到出现一次的数字.
//        Map<Integer, Integer> map=new HashMap<>();
//        for(int num:nums){
//            int count=map.getOrDefault(num,0);
//            map.put(num,count+1);
//        }
//        // 遍历该 map, 找到出现一次的数字.
//        for (Map.Entry<Integer, Integer> entry : map.entrySet()){
//            if(entry.getValue()==1){
//                return entry.getKey();
//            }
//        }
//        return 0;
//    }
    public int singleNumber(int[] nums) {
        // 通过异或的方式实现.
        int result = 0;
        for (int num : nums){
            result ^= num;
        }
        return result;
    }


    //给你一个长度为 n 的链表，每个节点包含一个额外增加的随机指针 random ，该指针可以指向链表中的任何节点或空节点。
    //构造这个链表的 深拷贝。 深拷贝应该正好由 n 个 全新 节点组成，其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点，并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点 。
    //例如，如果原链表中有 X 和 Y 两个节点，其中 X.random --> Y 。那么在复制链表中对应的两个节点 x 和 y ，同样有 x.random --> y 。
    //返回复制链表的头节点。
    //用一个由 n 个节点组成的链表来表示输入/输出中的链表。每个节点用一个 [val, random_index] 表示：
    //val：一个表示 Node.val 的整数。
    //random_index：随机指针指向的节点索引（范围从 0 到 n-1）；如果不指向任何节点，则为  null 。
    //你的代码 只 接受原链表的头节点 head 作为传入参数。
    public Node copyRandomList(Node head) {
        // 1. 创建 Map, key 是旧节点, value 是新节点.
        Map<Node, Node> map=new HashMap<>();
        // 2. 遍历旧链表, 依次创建新节点, 并插入 map 中.
        for (Node oldNode=head;oldNode != null; oldNode = oldNode.next) {
            Node newNode = new Node(oldNode.val);
            map.put(oldNode, newNode);
        }
        for (Node oldNode=head;oldNode != null; oldNode = oldNode.next) {
            Node newNode=map.get(oldNode);
            // 连接 next
            newNode.next=map.get(oldNode.next);
            // 连接 random
            newNode.random=map.get(oldNode.random);
        }
        return map.get(head);
    }


    //给你一个字符串 jewels 代表石头中宝石的类型，另有一个字符串 stones 代表你拥有的石头。 stones 中每个字符代表了一种你拥有的石头的类型，你想知道你拥有的石头中有多少是宝石。
    //
    //字母区分大小写，因此 "a" 和 "A" 是不同类型的石头。
    //输入：jewels = "aA", stones = "aAAbbbb"    输入：jewels = "z", stones = "ZZ"
    //输出：3                                    输出：0
    public int numJewelsInStones(String jewels, String stones) {
        Set<Character> set=new HashSet<>();
        for (char c : jewels.toCharArray()){
            set.add( c);
        }
        int count=0;
        for (char c : stones.toCharArray()){
//            if (set.contains( c)){
//                count++;
//            }
            // 使用 hash 来查询, 效率更高的.
            if (jewels.indexOf(c)>=0){
                count++;
            }
        }
        return count;
    }
}
